This description relates to managing synonyms in virtual-address caches.
Modern processors support ‘virtual memory’, which allows program instructions being executed by a CPU to refer to virtual addresses within a ‘virtual address space’ that is larger than a ‘physical address space’ that is defined by the size of main memory. Virtual memory involves address translation from one or more such virtual address spaces into a physical address space. The translation is performed using a ‘page table’ that stores mappings between virtual addresses and physical addresses at a granularity of memory pages (or simply ‘pages’).
Many modern processors also support hierarchical cache systems with multiple levels of cache, including one or more levels within the processor or within each core of a multi-core processor, starting with a level one (L1) cache, and one or more levels external to the processor or cores, up to a last level cache (LLC) that is accessed just before main memory is accessed. At each level of the hierarchy, the cache stores copies of a subset of data to speed access to that data by the processor relative to the speed of a higher level cache (or relative to the speed of the main memory for the LLC). Lower level caches are closer to the processor (or core), whereas higher level caches are further away from the processor (or core). The LLC is typically shared by all of the cores of a multi-core processor. At each level, the cache system will load blocks of data into entries and evict blocks of data from entries in units of ‘memory blocks’ (also called ‘cache lines’ or ‘cache blocks’). Each memory block includes a number of ‘words’ of data, each word consisting of a predetermined number of bytes. A memory page typically has data from many memory blocks.
A cache that is accessed using at least a portion of a virtual address and in some cases additional information such as context information (e.g., a virtual machine identifier, and an address space identifier, etc.) Such a cache is referred to herein as a ‘virtual-address cache’ or ‘VA cache’. Examples of a VA cache include caches that are accessed using an index and a tag, where the index is a portion of a virtual address and the tag is either another portion of the virtual address (in a virtually indexed, virtually tagged (VIVT) cache) or a portion of a corresponding physical address (in a virtually indexed, physically tagged (VIPT) cache). A VIVT cache is sometimes called a ‘virtual cache’. One issue that may arise with VA caches the presence of ‘synonyms’, which are different virtual addresses that are mapped, by different respective translations, to the same physical address (also called ‘aliasing’). There may be two or more different virtual addresses that all map to a common physical address, and are therefore synonyms of each other, or members of the same set of synonym virtual addresses. A cache that is allowed to store multiple synonym virtual addresses is potentially vulnerable to coherence violations unless certain precautions are taken.